package com.peng.leetcode.trie;

import java.util.ArrayList;
import java.util.List;

/**
 * FindWords
 *
 * @author: lupeng6
 * @create: 2021/1/29 17:27
 */
public class FindWords {

    public static void main(String[] args) {
        char[][] board = {{'a', 'b', 'c'}, {'a', 'e', 'd'}, {'a', 'f', 'g'}};
        String[] words = {"abcdefg", "gfedcbaaa", "eaabcdgfa", "befa", "dgc", "ade"};

//        String[] words = {"oath", "pea", "eat", "rain"};
//        char[][] board = {{'o', 'a', 'a', 'n'}, {'e', 't', 'a', 'e'}, {'i', 'h', 'k', 'r'}, {'i', 'f', 'l', 'v'}};
        System.out.println(new FindWords().findWords(board, words));
    }

    public List<String> findWords(char[][] board, String[] words) {
        int rows = board.length;
        int cols = board[0].length;

        List<String> result = new ArrayList<>();

        for (String word : words) {
            char firstChar = word.charAt(0);
            boolean[][] visited = new boolean[rows][cols];
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    if (firstChar == board[i][j]) {
                        boolean flag = findWords(board, i, j, word, 0, visited);
                        if (flag && !result.contains(word)) {
                            result.add(word);
                        }
                    }
                }
            }
        }

        return result;
    }

    private int[][] operations = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    private boolean findWords(char[][] board, int x, int y, String word, int index, boolean[][] visited) {
        if (index == word.length() - 1) {
            return true;
        }
        visited[x][y] = true;
        for (int[] operation : operations) {
            int newX = x + operation[0];
            int newY = y + operation[1];
            if (!isArea(board, newX, newY)) {
                continue;
            }
            if (board[newX][newY] != word.charAt(index + 1)) {
                continue;
            }
            if (visited[newX][newY]) {
                continue;
            }
            if (findWords(board, newX, newY, word, index + 1, visited)) {
                return true;
            }
        }
        visited[x][y] = false;
        return false;
    }

    private boolean isArea(char[][] board, int x, int y) {
        int rows = board.length;
        int cols = board[0].length;
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }
}
